
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 2117. -- [2010国家集训队]Crash的旅游计划 -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>2117: [2010国家集训队]Crash的旅游计划</h2><span class=green>Time Limit: </span>100 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>552 MB<br><span class=green>Submit: </span>10&nbsp;&nbsp;<span class=green>Solved: </span>1<br>[<a href='submitpage.php?id=2117'>Submit</a>][<a href='problemstatus.php?id=2117'>Status</a>][<a href='bbs.php?id=2117'>Discuss</a>]</center><h2>Description</h2><div class=content>眼看着假期就要到了，Crash由于长期切题而感到无聊了，因此他决定利用这个假期和好友陶陶一起出去旅游。
Crash和陶陶所要去的城市里有N (N > 1) 个景点，Crash用正整数1到N给景点标号。这些景点之间通过N &#8722; 1条无向道路相连，每条道路有一个长度，并且保证任意两个景点之间都有且仅有一条路径相连。
现在对于一个景点s，Crash和陶陶从s出发，然后访问一个景点序列{v0, v1, v2, … , vk}，其中v0就是s，且vi-1和vi(0 < i ≤ k)之间有道路相连。需要注意的是，陶陶和Crash访问的景点序列中不会只有景点s。为了使旅程不显得乏味，在一个景点序列里他们不会重复走某条道路。我们定义这个序列的旅游代价为经过道路的长度和。下面问题出现了：
陶陶：我们走一条景点数最多的景点序列吧。
Crash：倒，你想把我累死啊。
陶陶：谁叫你整天坐在电脑前面，不出来锻炼，这下子傻了吧，哈哈哈哈~~
Crash：不行，如果你非要走景点数最多的我就不陪你走了。
陶陶：笑喷油你很跳嘛！
Crash：这样吧，我们来写伸展树，如果我写的比你快，你就要听我的。
陶陶：这样不公平哎，我们来玩PES吧，当然你要让我选法国队，如果你输了你就要听我的。
Crash：倒，你这是欺负我，T_T~
陶陶：笑喷油好说话哎。
Crash：囧……
……
这样搞了半天，最终陶陶和Crash用很多次包剪锤决定出选择旅游代价第K小 的景点序列。
不过呢Crash和陶陶还没确定开始旅行的景点s，因此他希望你对于每个景点i，计算从景点i开始的景点序列中旅游代价第K小的值。
</div><h2>Input</h2><div class=content>共N行。
第1行包含一个字符和两个正整数，字符为ABCD中的一个，用来表示这个测试数据的类型（详见下面的数据规模和约定），另外两个正整数分别表示N和K (K < N)。
第2行至第N行，每行有三个正整数u、v和w (u, v ≤ N，w ≤ 10000)。表示u号景点和v号景点之间有一条道路，长度为w。
输入文件保证符合题目的约定，即任意两个景点之间都有且仅有一条路径相连。
</div><h2>Output</h2><div class=content>共N行，每行有一个正整数。第i行的正整数表示从i号景点开始的景点序列中旅游代价第K小的代价。</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>A 6 3<br />
1 2 2<br />
1 3 4<br />
1 4 3<br />
3 5 1<br />
3 6 2<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>4<br />
6<br />
4<br />
7<br />
5<br />
6<br />
</span></div><h2>HINT</h2>
			<div class=content><p>样例1中输出对应的景点序列分别为：1号景点是{1, 3}，2号景点是{2, 1, 3}，3号景点是{3, 1}，4号景点是{4, 1, 3}，5号景点是{5, 3, 1}，6号景点是{6, 3, 1}。<br />
<br />
保证每个景点到1号景点需要经过的道路数不超过30。	N ≤ 50000</p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=By 贾志鹏'>By 贾志鹏</a></p></div><center>[<a href='submitpage.php?id=2117'>Submit</a>][<a href='problemstatus.php?id=2117'>Status</a>][<a href='bbs.php?id=2117'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
